package hot100.logos11To20;

/**
 * @author logos
 * date 2025/7/10 16:42
 * @version v1.0
 * @Package hot100
 */
public class logos17 {

    /**
     * 17. 缺失的第一个正数
     * https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
     */
    class Solution {
        public int firstMissingPositive(int[] nums) {
            int l = 0;
            int r = nums.length;
            while (l < r) {
                if (nums[l] == l + 1) {
                    l++;
                } else if (nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l]) {
                    swap(nums, l, --r);
                } else {
                    swap(nums, l, nums[l] - 1);
                }
            }
            return l + 1;
        }

        private void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
}
